{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ### B树简介\n",
    "\n",
    "        B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。\n",
    "            ①根节点至少有两个子节点；\n",
    "            ②每个节点有M-1个key，并且以升序排列；\n",
    "            ③位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间；\n",
    "            ④非叶子结点的关键字个数=指向儿子的指针个数-1；\n",
    "            ⑤非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] ；\n",
    "            ⑥其它节点至少有M/2个子节点；\n",
    "            ⑦所有叶子结点位于同一层；\n",
    "         如：（M=3）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/B树.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " #### B树算法思想\n",
    "\n",
    "    B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；\n",
    "     B树的特性\n",
    "\n",
    "     1.关键字集合分布在整颗树中；\n",
    "     2.任何一个关键字出现且只出现在一个结点中；\n",
    "     3.搜索有可能在非叶子结点结束；\n",
    "     4.其搜索性能等价于在关键字全集内做一次二分查找；\n",
    "     5.自动层次控制；\n",
    "     由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为O(LogN)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# B树查找\n",
    "\n",
    "class BTree:  #B树\n",
    "    def __init__(self,value):\n",
    "        self.left=None\n",
    "        self.data=value\n",
    "        self.right=None\n",
    "\n",
    "    def insertLeft(self,value):\n",
    "        self.left=BTree(value)\n",
    "        return self.left\n",
    "\n",
    "    def insertRight(self,value):\n",
    "        self.right=BTree(value)\n",
    "        return self.right\n",
    "\n",
    "    def show(self):\n",
    "        print(self.data)\n",
    "\n",
    "\n",
    "def inorder(node):  #中序遍历：先左子树，再根节点，再右子树\n",
    "    if node.data:\n",
    "        if node.left:\n",
    "            inorder(node.left)\n",
    "        node.show()\n",
    "        if node.right:\n",
    "            inorder(node.right)\n",
    "\n",
    "\n",
    "def rinorder(node):  #倒中序遍历\n",
    "    if node.data:\n",
    "        if node.right:\n",
    "            rinorder(node.right)\n",
    "        node.show()\n",
    "        if node.left:\n",
    "            rinorder(node.left)\n",
    "\n",
    "def insert(node,value):\n",
    "    if value > node.data:\n",
    "        if node.right:\n",
    "            insert(node.right,value)\n",
    "        else:\n",
    "            node.insertRight(value)\n",
    "    else:\n",
    "        if node.left:\n",
    "            insert(node.left,value)\n",
    "        else:\n",
    "            node.insertLeft(value)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "中序遍历（从小到大排序 ）\n",
      "2\n",
      "4\n",
      "11\n",
      "22\n",
      "33\n",
      "33\n",
      "34\n",
      "55\n",
      "88\n",
      "221\n",
      "倒中序遍历（从大到小排序）\n",
      "221\n",
      "88\n",
      "55\n",
      "34\n",
      "33\n",
      "33\n",
      "22\n",
      "11\n",
      "4\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "l=[88,11,2,33,22,4,55,33,221,34]\n",
    "Root=BTree(l[0])\n",
    "node=Root\n",
    "for i in range(1,len(l)):\n",
    "    insert(Root,l[i])\n",
    "\n",
    "print(\"中序遍历（从小到大排序 ）\")\n",
    "inorder(Root)\n",
    "print(\"倒中序遍历（从大到小排序）\")\n",
    "rinorder(Root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### B+ 树简介\n",
    "\n",
    "    B+树是B-树的变体，也是一种多路搜索树：\n",
    "       1.其定义基本与B-树同，除了：\n",
    "       2.非叶子结点的子树指针与关键字个数相同；\n",
    "       3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树\n",
    "       4.B-树是开区间；\n",
    "       5.为所有叶子结点增加一个链指针；\n",
    "       6.所有关键字都在叶子结点出现；\n",
    "\n",
    "    如：（M=3）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/B+树.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### B+树算法思想\n",
    "\n",
    "    B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；\n",
    "    B+树的特性\n",
    "\n",
    "      1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；\n",
    "      2.不可能在非叶子结点命中；\n",
    "      3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；\n",
    "      4.更适合文件索引系统；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
